package baseclass.k_array;

/**
 * 给定一个数组arr， 返回所有子序列的累加和中， 最大的累加和
 *
 * @date 2020/3/4 17:50
 */
public class Code01_SubArrayMaxSum1 {
    /**
     * 给定一个数组arr， 返回所有子序列的累加和中， 最大的累加和
     * 子序列：任意不连续或连续的子串
     * 方式1：
     * 要当前位置或者不要，递归所有可能性，取最大
     * 方式2：
     * case1：全为负数，则直接返回最大
     * case2：有正有负，则把所有的正数加起来.或者用递归
     */
    public static int getMaxSum(int[] arr, int index, int sum) {
        if (arr == null || index == arr.length) {
            return sum;
        }
        return Math.max(
                getMaxSum(arr, index + 1, sum),
                getMaxSum(arr, index + 1, sum + arr[index])
        );
    }

    public static int getMaxSum2(int[] arr) {
        if (arr == null) {
            return 0;
        }
        boolean allNegative = true;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= 0) {
                allNegative = false;
                break;
            }
        }
        //找数组最大
        if (allNegative) {
            int min = arr[0];
            for (int i = 0; i < arr.length; i++) {
                min = Math.min(min, arr[i]);
            }
            return min;
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i] > 0 ? arr[i] : 0;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, -1, 3, 0};
        int[] arr2 = {-7, -2, -1, -3, -5};
        //注意：如果写成index = 0，sum = 0，那么会破坏都是负数的情况。如果写成index=0，sum = arr[0]，那么会多加一次arr【0】
        System.out.println(getMaxSum(arr1, 1, arr1[0]));
        System.out.println(getMaxSum2(arr1));
        System.out.println(getMaxSum(arr2, 1, arr2[0]));
        System.out.println(getMaxSum2(arr2));
    }

}
